package HOT;

/**
 * Author  zxy
 * Date  2023/6/20 下午 2:36
 */
public class Search {
    public int search(int[] arr, int target) {
        int len = arr.length;

        if (len == 0) {
            return -1;
        }
        else if (arr[0] == target) {
            return 0;
        }

        int l = 0;
        int r = len - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;

            if (arr[mid] == target) {
                while (mid > 0 && arr[mid - 1] == target) {
                    mid--;
                }
                return mid;
            }

            // 右边有序
            if (arr[mid] < arr[r]) {
                // 在右边
                if (arr[mid] < target && target <= arr[r]) {
                    l = mid + 1;
                }
                // 左边
                else {
                    r = mid - 1;
                }
            }
            // 左边有序
            else if (arr[mid] > arr[r]){
                // 左边
                if (arr[l] <= target && target < arr[mid]) {
                    r = mid - 1;
                }
                // 右边
                else {
                    l = mid + 1;
                }
            }
            // 相等，忽略右边
            else {
                r--;
            }
        }

        return -1;
    }
}
